package com.fresh.everynew.fp.lcode;


import org.junit.Test;

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int... val) {
        ListNode _this = this;
        for (int i : val) {
            _this.val = i;
            _this.next = new ListNode();
            _this = _this.next;
        }
        deleteLast(_this);
    }

    public void deleteLast(ListNode l) {
        ListNode _this = this;
        while (_this.next != l) {
            _this = _this.next;
        }
        _this.next = null;
    }

    @Override
    public String toString() {
        return val + ", " + (next != null ? next.toString() : "");
    }
}

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i < len && ((i>0&&nums[i]!=nums[i-1]) || i==0); i++) {
            for (int j = i+1;j < len && ((j>i+1&&nums[j]!=nums[j-1]) || j==i+1); j++) {
                for(int k = len-1; k > j && ((k>j+1&&nums[k]!=nums[k-1]) || k==j+1); k--){
                    if(nums[i] + nums[j] + nums[k] == 0){
                        List<Integer> subList = new ArrayList<>();
                        subList.add(nums[i]);
                        subList.add(nums[j]);
                        subList.add(nums[k]);
                        ans.add(subList);
                    }
                }
            }
        }
        return ans;

    }

    public List<Integer> pathInZigZagTree(int label) {
        int level = level(label);
        int levelFact = level % 2;
        int dis = label - (int) Math.pow(2, level);
        int ll = label;
        int lr = (int) Math.pow(2, level + 1) - 1 - dis;

        List<Integer> ans = new ArrayList<Integer>();
        ans.add(label);
        for (int cur = level; cur > 0; ) {
            ll = pre(ll);
            lr = pre(lr);
            cur--;
            ans.add(cur % 2 == levelFact ? ll : lr);
        }
        Collections.reverse(ans);
        return ans;
    }

    public int level(int label) {
        int level = 1;

        if (label == 1)
            return 0;
        while (pre(label) != 1) {
            label = pre(label);
            level++;
        }
        return level;
    }

    public int pre(int label) {
        if (label == 1) {
            return 1;
        }
        return label / 2;
    }

    @Test
    public void test() {
        System.out.println(threeSum(new int[]{0,0,0,0}));
/*        "mississippi"
          "mis*is*p*."   */
//        System.out.println(findMedianSortedArrays(new int[]{0,0,0,0,0}, new int[]{-1,0,0,0,0,0,1}));
//        System.out.println(findMedianSortedArrays1(new int[]{3}, new int[]{-2,-1}));
//        ListNode l1 = new ListNode(9,9,9,9,9,9,9);
//        ListNode l2 = new ListNode(9,9,9,9);
//        System.out.println(addTwoNumbers(l1,l2));
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode start = l2;
        while (l1 != null && l2 != null) {
            add(l2, l1.val);
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode tail = start;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = l1;
        return start;
    }

    public ListNode add(ListNode l, int val) {
        if (l == null)
            l = new ListNode();
        if (val == 0)
            return l;

        l.val = l.val + val;

        if (l.val > 9) {
            l.val = l.val % 10;
            if (l.next == null) {
                l.next = new ListNode();
            }
            add(l.next, 1);
        }
        return l;
    }
}